import pygame  
import sys
import time
from collections import deque

# 初始化pygame  
pygame.init()

pygame.display.set_caption("地图连通检测")
  
# 设置屏幕大小  
screen_width, screen_height = 500, 500  
screen = pygame.display.set_mode((screen_width, screen_height))  
  
# 设置网格大小  
grid_size = 10  
cell_width = screen_width // grid_size
cell_height = screen_height // grid_size

COLOR_WHITE = (255, 255, 255)
COLOR_BLACK = (0, 0, 0)
COLOR_RED = (255, 0, 0)

# 网格颜色  
grid_colors = [[COLOR_WHITE] * grid_size for _ in range(grid_size)]

def is_interconnected(grid, start_row, start_col, end_row, end_col):  
    # 网格的行数和列数  
    rows, cols = len(grid), len(grid[0])  
      
    # 定义四个方向的行列偏移量  
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  
      
    # 创建一个队列用于BFS  
    queue = deque([(start_row, start_col, 0)])  # (row, col, steps)  
      
    # 创建一个与网格大小相同的布尔矩阵来跟踪访问状态  
    visited = [[False] * cols for _ in range(rows)]  
    visited[start_row][start_col] = True  
      
    while queue:  
        row, col, steps = queue.popleft()  
          
        # 检查是否到达了目标格子  
        if row == end_row and col == end_col:  
            return True  
          
        # 遍历所有相邻格子  
        for dr, dc in directions:  
            new_row, new_col = row + dr, col + dc
            
            # 检查边界条件和颜色以及是否已访问  
            if new_row < 0 or new_row >= rows:
                continue
            if new_col < 0 or new_col >= cols:
                continue
            if visited[new_row][new_col]:
                continue
            if grid[new_row][new_col] == COLOR_BLACK:
                continue
            
            visited[new_row][new_col] = True  
            queue.append((new_row, new_col, steps + 1))
      
    # 如果队列为空且未找到目标格子，则返回False  
    return False

def draw_conflic_grids():
    """画冲突格子"""
    grid_list = []
    for row in range(grid_size):  
        for col in range(grid_size):  
            color = grid_colors[row][col]
            if color == COLOR_RED:
                grid_colors[row][col] = COLOR_WHITE
            elif color != COLOR_WHITE:
                continue
            
            # 先假定为黑
            grid_colors[row][col] = COLOR_BLACK

            r1,r2 = row - 1,row + 1
            c1,c2 = col - 1,col + 1
            
            grid_list.clear()
            if c1 >= 0 and grid_colors[row][c1] != COLOR_BLACK:
                grid_list.append([row,c1])
            if r1 >= 0 and grid_colors[r1][col] != COLOR_BLACK:
                grid_list.append([r1,col])
            if c2 < grid_size and grid_colors[row][c2] != COLOR_BLACK:
                grid_list.append([row,c2])
            if r2 < grid_size and grid_colors[r2][col] != COLOR_BLACK:
                grid_list.append([r2,col])

            is_flag = True
            for i in range(len(grid_list)):
                for j in range(len(grid_list)):
                    if i >= j:
                        continue
                r1,c1 = grid_list[i][0],grid_list[i][1]
                r2,c2 = grid_list[j][0],grid_list[j][1]
                if is_flag == False:
                    break
                is_flag = is_interconnected(grid_colors, r1, c1, r2, c2)
            
            if is_flag == False:
                grid_colors[row][col] = COLOR_RED
            else:
                grid_colors[row][col] = COLOR_WHITE

# 游戏主循环  
running = True  
while running:  
    # 绘制格子（带有颜色）  
    for row in range(grid_size):  
        for col in range(grid_size):  
            color = grid_colors[row][col]  
            pygame.draw.rect(screen, color, (col * cell_width, row * cell_height, cell_width, cell_height))
    
    for event in pygame.event.get():  
        if event.type == pygame.QUIT:  
            running = False  
        elif event.type == pygame.MOUSEBUTTONDOWN:  
            # 处理鼠标点击事件  
            mouse_x, mouse_y = event.pos  
            x_idx = mouse_x // cell_width  
            y_idx = mouse_y // cell_height  
              
            if 0 <= x_idx < grid_size and 0 <= y_idx < grid_size:
                color = grid_colors[y_idx][x_idx]
                # 原先白色，变成黑色
                if color == COLOR_RED:
                    break
                elif color == COLOR_WHITE:
                    grid_colors[y_idx][x_idx] = COLOR_BLACK
                # 原先黑色，变成白色
                elif color == COLOR_BLACK:
                    grid_colors[y_idx][x_idx] = COLOR_WHITE                    
            # 画冲突格子
            draw_conflic_grids()
        elif event.type == pygame.KEYDOWN:
            if event.key == pygame.K_r:
                grid_colors = [[COLOR_WHITE] * grid_size for _ in range(grid_size)]  # 重置网格颜色
    
    # 绘制网格线  
    for col in range(grid_size + 1):  
        pygame.draw.line(screen, (0, 80, 20), (col * cell_width, 0), (col * cell_width, screen_height), 1)  
    for row in range(grid_size + 1):  
        pygame.draw.line(screen, (0, 80, 20), (0, row * cell_height), (screen_width, row * cell_height), 1)  
    
    font = pygame.font.Font(None, 16)  # 创建一个字体对象  
    for i in range(grid_size):  
        text_x = i * cell_width + cell_width // 2 - 10  # 列号水平居中  
        text_y = 5  # 行号在顶部  
        text = font.render(str(i+1), True, (255, 165, 0))
        screen.blit(text, (text_x, text_y))  
        
        if i == 0:
            continue
        
        text_x = 5  # 列号在左侧  
        text_y = i * cell_height + cell_height // 2 - 5  # 行号垂直居中  
        text = font.render(str(i+1), True, (255, 165, 0))
        screen.blit(text, (text_x, text_y))
    
    # 更新屏幕显示  
    pygame.display.flip()
    time.sleep(0.1)
  
# 退出pygame  
pygame.quit()  
sys.exit()